package MyDP;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 368. 最大整除子集
 * 给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
 *
 *     answer[i] % answer[j] == 0 ，或
 *     answer[j] % answer[i] == 0
 *
 * 如果存在多个有效解子集，返回其中任何一个均可。
 */
public class Leetcode0368_no {

    //返回一个最长递增子序列
    public static List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> answer = new ArrayList<>();
        if (nums.length <= 0) return answer;
        Arrays.sort(nums);
        // dp 数组
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        // 记录他的前一位是谁
        int[] pre = new int[nums.length];
        Arrays.fill(pre, -1);
        // 最长的长度
        int res= -1;
        int max_index = 0;
        for(int i=1; i<nums.length; i++){
            for(int j=0; j< i; j++){
                if(nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]){
                    dp[i] = dp[j] + 1;
                    pre[i] = j;
                }
                if(dp[i] > res){
                    res = dp[i];
                    max_index = i;
                }
            }
        }
//        for(int ss : pre){
//            System.out.print(ss + " ");
//        }

        while (max_index !=-1){
            answer.add(nums[max_index]);
            max_index = pre[max_index];
        }

        return answer;

    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,4,8,12};
        List<Integer> integers = largestDivisibleSubset(nums);
        for(int ss: integers){
            System.out.print(ss + " ");
        }
    }
}
